package org.example.Soution004;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SkillNextArrange {
    public static void main(String[] args) {
        SkillNextArrange obj = new SkillNextArrange();
        int[] nums=new int[]{2,3,1};
        obj.nextPermutation(nums);
    }

    public void nextPermutation1(int[] nums) {
        //直接一个list，支持快速查找就可以了
        int n=nums.length;
        List<Integer> list=new ArrayList<>();
        list.add(nums[n-1]);int size=1;
        for(int i=n-2;i>=0;i--){
            if(nums[i]>=list.get(size-1)){
                list.add(nums[i]);
                size++;
            }else{
                int flag=i;int tmp=nums[i];
                for(int j=size-1;j>=0;j--){
                    if (nums[i]<list.get(j)){
                        flag++;
                    }else{
                        break;
                    }
                }
                flag=n-1-flag;
                nums[i]=list.get(flag);
                for(int j=0;j<=flag-1;j++){
                    nums[i+j+1]=list.get(j);
                }
                nums[i+flag+1]=tmp;
                for(int j=flag+1;j<list.size();j++){
                    nums[i+j+1]=list.get(j);
                }
                System.out.println(Arrays.toString(nums));
                return;
            }
        }
        //反转数组
        int left=0,right=n-1;
        while(left<right){
            int tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;
            left++;
            right--;
        }
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {
        int n=nums.length;
        //要被置换后的数列是其及其之前数字不变情况下最大的情况，置换后需要把后面变成最小的情况
        //为了保证变幻幅度尽可能小，首先找第一个不符合递增（头←尾）的数字
        int i=n-2;
        while(i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if(i>=0){
            //找到第一个比要被置换的数字大的数字
            int j=n-1;
            while(j>i&&nums[i]>=nums[j]){
                j--;
            }
            //置换
            swap(nums,i,j);
        }
        //将被置换后的数列倒置
        Reverse(nums,i+1,nums.length-1);
//        System.out.println(Arrays.toString(nums));
    }

    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }

    public void Reverse(int[] nums,int i,int j){
        int start=i,end=j;
        while(start<end){
            swap(nums,start,end);
            start++;
            end--;
        }
    }
}
